/**************************************************//*!
 *
 * \file    primes.cpp
 * \brief   Algorithms about number theory
 *
 *  This file is ported from fftw, originally written by Matteo Frigo
 *
 * \author  Terence Wu
 * \date    Sep. 2009
 *
 ****************************************************/


#include "ifftgpu.h"
#include "primes.h"

/* integer square root.  Return floor(sqrt(N)) */
int isqrt(int n)
{
    int guess, iguess;

    ASSERT(n >= 0);
    if (n == 0) return 0;

    guess = n; iguess = 1;

    do {
        guess = (guess + iguess) / 2;
        iguess = n / guess;
    } while (guess > iguess);

    return guess;
}

int get_radix(int r, int n)
{
    if (r==0) {
        r = isqrt(n);
    }else{
        r--;
    }
    for (; r > 1; r--) {
        if (DIVIDES(r, n)) {
            break;
        }
    }
    return ((r > 1) ? r : 1);
}
